package 算法.leetcode.array;

import org.junit.Test;

/**
 * 用 dp[i]dp[i] 表示前 ii 间房屋能偷窃到的最高总金额，那么就有如下的状态转移方程：
 * <p>
 * \textit{dp}[i] = \max(\textit{dp}[i-2]+\textit{nums}[i], \textit{dp}[i-1])
 * dp[i]=max(dp[i−2]+nums[i],dp[i−1])
 * <p>
 * 作者：LeetCode-Solution
 * 链接：https://leetcode-cn.com/problems/house-robber/solution/da-jia-jie-she-by-leetcode-solution/
 * 来源：力扣（LeetCode）
 * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
 *
 * @author lchenglong
 * @date 2020/12/9
 */
public class Rob {

    @Test
    public void test() {
//        int[] nums = new int[]{2,7,9,3,1};
//        System.out.println(rob(nums));

//        Integer.toBinaryString(175);
        System.out.println(Integer.toBinaryString(175));
    }

    /**
     * 偷窃第 k 间房屋，那么就不能偷窃第 k−1 间房屋，偷窃总金额为前k−2间房屋的最高总金额与第 k 间房屋的金额之和。
     * <p>
     * 不偷窃第 k 间房屋，偷窃总金额为前 k−1 间房屋的最高总金额。
     * <p>
     * 用 dp[i] 表示前 i 间房屋能偷窃到的最高总金额，那么就有如下的状态转移方程：
     * <p>
     * dp[i]=max(dp[i−2]+nums[i],dp[i−1])
     * <p>
     * 边界条件如下
     * dp[0]=nums[0] 只有一间房屋，则偷窃该房屋
     * dp[1]=max(nums[0],nums[1]) 只有两间房屋，选择其中金额较高的房屋进行偷窃
     *
     * @return
     */
    public int rob(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int n = nums.length;
        if (n == 1) {
            return nums[0];
        }
        int[] dp = new int[n];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);
        for (int i = 2; i < n; i++) {
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
        }
        return dp[n - 1];
    }


    public static class MyRunnable implements Runnable {

        public void run() {
            System.out.println("MyRunnable is run start");
        }
    }

    public static class MyRunnable2 implements Runnable {

        private Object object;

        public MyRunnable2(Object object) {
            this.object = object;
        }

        public void run() {
            System.out.println("MyRunnable2 is run start");
            try {
                synchronized (object) {
                    Thread.sleep(2000);
                    object.notify();
                }
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
            System.out.println("MyRunnable2 is run end");
        }
    }

    public static class MyThread extends Thread {
        int i = 0;
        @Override
        public void run() {
            while (true) {
                System.out.println(i);
                try {
                    Thread.sleep(1000);
                } catch (InterruptedException e) {
                    System.out.println("中断异常被捕获了");
                    return;
                }
                i++;
            }
        }
    }

    public static void main(String[] args) throws InterruptedException {
        for (int i=0 ;i<10;i++) {
            MyThread thread = new MyThread();
            thread.start();
            Thread.sleep(3000);
            thread.interrupt();
        }
    }


}
